{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Music Playlists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numMusicPlaylists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #播放列表的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你的音乐播放器里有 <code>n</code> 首不同的歌，在旅途中，你计划听 <code>goal</code> 首歌（不一定不同，即，允许歌曲重复）。你将会按如下规则创建播放列表：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每首歌 <strong>至少播放一次</strong> 。</li>\n",
    "\t<li>一首歌只有在其他 <code>k</code> 首歌播放完之后才能再次播放。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你 <code>n</code>、<code>goal</code> 和 <code>k</code> ，返回可以满足要求的播放列表的数量。由于答案可能非常大，请返回对 <code>10<sup>9</sup> + 7</code> <strong>取余</strong> 的结果。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, goal = 3, k = 1\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>有 6 种可能的播放列表。[1, 2, 3]，[1, 3, 2]，[2, 1, 3]，[2, 3, 1]，[3, 1, 2]，[3, 2, 1] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, goal = 3, k = 0\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>有 6 种可能的播放列表。[1, 1, 2]，[1, 2, 1]，[2, 1, 1]，[2, 2, 1]，[2, 1, 2]，[1, 2, 2] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, goal = 3, k = 1\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>有 2 种可能的播放列表。[1, 2, 1]，[2, 1, 2] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= k &lt; n &lt;= goal &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-music-playlists](https://leetcode.cn/problems/number-of-music-playlists/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-music-playlists](https://leetcode.cn/problems/number-of-music-playlists/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n3\\n1', '2\\n3\\n0', '2\\n3\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        mod, res = 1000000007, [0 for _ in range(n + 1)]\n",
    "        res[1] = n\n",
    "        for i in range(2, goal + 1):\n",
    "            tmp = [0 for _ in range(n + 1)]\n",
    "            if i <= k + 1: tmp[i] = (res[i - 1] * (n - i + 1)) % mod\n",
    "            else:\n",
    "                for j in range(k + 1, n + 1):\n",
    "                    tmp[j] = (res[j] * (j - k) + res[j - 1] * (n - j + 1)) % mod\n",
    "            res = tmp\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        pre = [0] * (n+1)\n",
    "        pre[0] = 1\n",
    "        for i in range(1, goal+1):\n",
    "            cur = [0] * (n+1)\n",
    "            cnt = i if i < n else n\n",
    "            for j in range(1, cnt+1):\n",
    "                # 新歌\n",
    "                cur[j] = pre[j-1]*(n-j+1)\n",
    "                # 旧歌\n",
    "                if j > k:\n",
    "                    cur[j] += pre[j]*(j-k)\n",
    "                cur[j] %= mod\n",
    "            pre = cur\n",
    "        return pre[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, m: int, k: int) -> int:\n",
    "        pre = [0] * (n+1)\n",
    "        pre[0] = 1\n",
    "        for i in range(1, m+1):\n",
    "            cur = [0] * (n+1)\n",
    "            cnt = min(i, n)\n",
    "            for j in range(1, cnt+1):\n",
    "                cur[j] = pre[j-1] * (n-j+1)\n",
    "                if j > k:\n",
    "                    cur[j] += pre[j] * (j - k)\n",
    "                cur[j] %= MOD\n",
    "            pre = cur\n",
    "        return pre[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# dp[i][j] := ways to construct playlist of i length with j distinct songs, j <= i\r\n",
    "# dp[0][0] = 1\r\n",
    "# dp[i + 1][j + 1] = dp[i][j] * (n - j) + dp[i][j + 1] * (j - k + 1), if j > k\r\n",
    "# select a new song out of n - j + 1 unselect songs, or select an old song out of j - k previous songs\r\n",
    "dp = [0] * 101\r\n",
    "class Solution:\r\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\r\n",
    "        for i in range(n + 1): dp[i] = 0\r\n",
    "        dp[1] = n\r\n",
    "\r\n",
    "        for i in range(1, goal):\r\n",
    "            for j in range(min(n - 1, i), -1, -1):\r\n",
    "                dp[j + 1] *= max(0, j - k + 1)\r\n",
    "                dp[j + 1] += dp[j] * (n - j)\r\n",
    "                dp[j + 1] %= 1000000007 \r\n",
    "\r\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        mod, res = 1000000007, [0 for _ in range(n + 1)]\n",
    "        res[1] = n\n",
    "        for i in range(2, goal + 1):\n",
    "            tmp = [0 for _ in range(n + 1)]\n",
    "            if i <= k + 1: tmp[i] = (res[i - 1] * (n - i + 1)) % mod\n",
    "            else:\n",
    "                for j in range(k + 1, n + 1):\n",
    "                    tmp[j] = (res[j] * (j - k) + res[j - 1] * (n - j + 1)) % mod\n",
    "            res = tmp\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 1 \n",
    "        for i in range(1, goal + 1):\n",
    "            new = [0] * (n + 1)\n",
    "            for j in range(1, min(i, n) + 1):\n",
    "                new[j] += dp[j - 1] * (n - j + 1)\n",
    "                new[j] += dp[j] * max(j - k, 0)\n",
    "            dp = new \n",
    "        return dp[-1] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        mod,opt,ans=1000000007,1,0\n",
    "        fac,inv=[0]*(n+1),[0]*(n+1)\n",
    "        fac[0],inv[0]=1,1\n",
    "        for i in range(1,n+1):fac[i]=fac[i-1]*i%mod\n",
    "        inv[n]=pow(fac[i],mod-2,mod)\n",
    "        for i in range(n,1,-1):inv[i-1]=inv[i]*i%mod\n",
    "        for m in range(n,k,-1):\n",
    "            f=1\n",
    "            for i in range(k):f=f*(m-i)%mod\n",
    "            for i in range(k,goal):f=f*(m-k)%mod\n",
    "            f=f*fac[n]%mod*inv[m]%mod*inv[n-m]%mod\n",
    "            ans=(ans+f*opt)%mod;opt*=-1\n",
    "        return (ans+mod)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, goal + 1):\n",
    "            tmp = [0] * (n + 1)\n",
    "            for j in range(1, n + 1):\n",
    "                tmp[j] = (tmp[j] + dp[j - 1] * (n - j + 1)) % MOD\n",
    "                tmp[j] = (tmp[j] + dp[j] * max(0, j - k)) % MOD\n",
    "            dp = tmp\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "\n",
    "        # dp[i][j]: 总曲目为i时, 播放了j首不同的歌，对应的可能的最大播放列表数量\n",
    "        # 状态压缩，压缩掉i的维度，dp[j]: 播放了j首不同的歌，可能的播放列表数量\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        pre = [0] * (n + 1)\n",
    "        pre[0] = 1\n",
    "\n",
    "        # foreach 容量\n",
    "        for i in range(1, goal + 1):\n",
    "            cur = [0] * (n + 1)\n",
    "\n",
    "            # 最多可选的歌的数量\n",
    "            max_songs = i if i < n else n\n",
    "\n",
    "            for j in range(1, max_songs + 1):\n",
    "                # j 影响之后添加的新歌和旧歌的数量\n",
    "\n",
    "                # 选择新歌，之前播放了j - 1首不同的歌，共有(n - j + 1)首\n",
    "                cur[j] = pre[j - 1] * (n - j + 1)\n",
    "\n",
    "                # 选择旧歌，共有(j-k)首\n",
    "                if j > k:\n",
    "                    cur[j] += pre[j] * (j - k)\n",
    "\n",
    "                cur[j] %= MOD\n",
    "            \n",
    "            pre = cur\n",
    "        \n",
    "        return pre[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        \n",
    "        def factorial(num):\n",
    "            a = 1\n",
    "            for i in range(1, num + 1):\n",
    "                a *= i\n",
    "            return a\n",
    "\n",
    "        dp = [[0 for _ in range(goal - n + 1)] for __ in range(n - k)]\n",
    "        if goal - n == 0:\n",
    "            return factorial(n)% (10**9+7)\n",
    "        dp[0][1] = 1\n",
    "        for i in range(n - k):\n",
    "            dp[i][0] = 1\n",
    "        for j in range(1,goal-n+1):\n",
    "            dp[0][j] = 1\n",
    "        for i in range(1, n - k):\n",
    "            for j in range(1, goal - n + 1):\n",
    "                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] * (i + 1)\n",
    "\n",
    "        return (factorial(n)*dp[n - k - 1][goal - n]) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        # dp[S] at time P = <S, P> as discussed in article\n",
    "        L = goal\n",
    "        dp = [1] * (L-n+1)\n",
    "        for p in range(2, n-k+1):\n",
    "            for i in range(1, L-n+1):\n",
    "                dp[i] += dp[i-1] * p\n",
    "\n",
    "        # Multiply by n!\n",
    "        ans = dp[-1]\n",
    "        for k in range(2, n+1):\n",
    "            ans *= k\n",
    "        return ans % (10**9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1,goal + 1):\n",
    "            for j in range(n,0,-1):\n",
    "                dp[j] = dp[j] * max(j - k,0)\n",
    "                dp[j] += dp[j - 1] * (n - j + 1)\n",
    "                dp[j] %= MOD\n",
    "            dp[0] = 0\n",
    "        return dp[-1]\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i == 0:\n",
    "        #         return j == 0\n",
    "        #     ans = dfs(i - 1,j - 1) * (n - j + 1)\n",
    "        #     ans += dfs(i - 1,j) * max(j - k, 0)\n",
    "        #     return ans % MOD\n",
    "        # return dfs(goal,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        dp = [[0] * (n + 1) for _ in range(2)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,goal + 1):\n",
    "            dp[i % 2][0] = 0\n",
    "            for j in range(1,n + 1):\n",
    "                dp[i % 2][j] = dp[(i - 1) % 2][j - 1] * (n - j + 1)\n",
    "                dp[i % 2][j] += dp[(i - 1) % 2][j] * max(j - k,0)\n",
    "                dp[i % 2][j] %= MOD\n",
    "        return dp[goal % 2][n]\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i == 0:\n",
    "        #         return j == 0\n",
    "        #     ans = dfs(i - 1,j - 1) * (n - j + 1)\n",
    "        #     ans += dfs(i - 1,j) * max(j - k, 0)\n",
    "        #     return ans % MOD\n",
    "        # return dfs(goal,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        dp = [[0] * (n + 1) for _ in range(2)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,goal + 1):\n",
    "            dp[i % 2][0] = 0\n",
    "            for j in range(1,n + 1):\n",
    "                dp[i % 2][j] = dp[(i - 1) % 2][j - 1] * (n - j + 1)\n",
    "                dp[i % 2][j] += dp[(i - 1) % 2][j] * max(j - k,0)\n",
    "                dp[i % 2][j] %= MOD\n",
    "        return dp[goal % 2][-1]\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i == 0:\n",
    "        #         return j == 0\n",
    "        #     ans = dfs(i - 1,j - 1) * (n - j + 1)\n",
    "        #     ans += dfs(i - 1,j) * max(j - k, 0)\n",
    "        #     return ans % MOD\n",
    "        # return dfs(goal,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "\n",
    "        # dp[i][j]: 总曲目为i时, 播放了j首不同的歌，对应的可能的最大播放列表数量\n",
    "        # 状态压缩，压缩掉i的维度，dp[j]: 播放了j首不同的歌，可能的播放列表数量\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        pre = [0] * (n + 1)\n",
    "        pre[0] = 1\n",
    "\n",
    "        # foreach 容量\n",
    "        for i in range(1, goal + 1):\n",
    "            cur = [0] * (n + 1)\n",
    "\n",
    "            # 最多可选的歌的数量\n",
    "            max_songs = i if i < n else n\n",
    "\n",
    "            for j in range(1, max_songs + 1):\n",
    "                # j 影响之后添加的新歌和旧歌的数量\n",
    "\n",
    "                # 选择新歌，之前播放了j - 1首不同的歌，共有(n - j + 1)首\n",
    "                cur[j] = pre[j - 1] * (n - j + 1)\n",
    "\n",
    "                # 选择旧歌，共有(j-k)首\n",
    "                if j > k:\n",
    "                    cur[j] += pre[j] * (j - k)\n",
    "\n",
    "                cur[j] %= MOD\n",
    "            \n",
    "            pre = cur\n",
    "        \n",
    "        return pre[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        dp = [[0] * (n + 1) for _ in range(goal + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,goal + 1):\n",
    "            for j in range(1,n + 1):\n",
    "                dp[i][j] = dp[i - 1][j - 1] * (n - j + 1)\n",
    "                dp[i][j] += dp[i - 1][j] * max(j - k,0)\n",
    "                dp[i][j] %= MOD\n",
    "        return dp[-1][-1]\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i == 0:\n",
    "        #         return j == 0\n",
    "        #     ans = dfs(i - 1,j - 1) * (n - j + 1)\n",
    "        #     ans += dfs(i - 1,j) * max(j - k, 0)\n",
    "        #     return ans % MOD\n",
    "        # return dfs(goal,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\r\n",
    "class Solution:\r\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\r\n",
    "        f=[[0]*(n+1) for _ in range(goal+1)]\r\n",
    "        f[0][0]=1\r\n",
    "        for i in range(1,goal+1):\r\n",
    "            for j in range(1,n+1):\r\n",
    "                f[i][j]=f[i-1][j-1]*(n-j+1)\r\n",
    "                if j>k:\r\n",
    "                    f[i][j]+=f[i-1][j]*(j-k)\r\n",
    "                f[i][j]%=10**9+7\r\n",
    "        return f[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        dp = [[0] * (goal+1) for _ in range(n+1)]\n",
    "\n",
    "        dp[0][0] = 1\n",
    "        \n",
    "        # 考虑最后一首歌\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, goal+1):\n",
    "                # 最后一首歌之前没播放过\n",
    "                dp[i][j] = dp[i-1][j-1] * (n-i+1)\n",
    "                # 播放过\n",
    "                dp[i][j] += dp[i][j-1] * max((i-k), 0)\n",
    "                dp[i][j] %= mod\n",
    "\n",
    "\n",
    "        return dp[n][goal]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, N: int, L: int, K: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        # dp[i][j] 表示用j首不同的歌填充长度为i的歌单\n",
    "        dp = [[0] * (N + 1) for _ in range(L + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, L + 1):\n",
    "            for j in range(1, N + 1):\n",
    "                # 分成两种情况\n",
    "                # 如果当前的歌和前面的都不一样，歌单前i-1首歌只包括了j-1首不同的歌曲，\n",
    "                # 那么当前的选择有dp[i-1][j-1] * (N-j+1)\n",
    "                # 如果当前的歌和前面的有重复的，那最近的K首必然是不能重复的，\n",
    "                # 所以选择就是dp[i-1][j] * max(0, j-K)\n",
    "                dp[i][j] = (dp[i-1][j-1] * (N - j + 1) + dp[i-1][j] * max(0, j - K)) % mod\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, m: int, k: int) -> int:\n",
    "        # f[i][j] 前i首听了j首，且满足要求的播放列表数量。\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, min(n, i) + 1):\n",
    "                f[i][j] = (f[i - 1][j - 1] * (n - (j - 1)) + f[i - 1][j] * max(j - k, 0)) % MOD\n",
    "        return f[m][n] % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        # 播放列表长度为i，j首不同的歌\n",
    "        dp = [[0]*(n+1) for _ in range(goal+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,goal+1):\n",
    "            for j in range(1,n+1):\n",
    "                dp[i][j] = dp[i-1][j-1] * (n-j+1) + \\\n",
    "                            dp[i-1][j]*max(j-k,0)\n",
    "                dp[i][j]%=MOD\n",
    "        return dp[-1][-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[0] * (n + 1) for _ in range(goal + 1)]\n",
    "        dp[0][0] = 1\n",
    "        # dp[i][j] = dp[i - 1][j - 1] * (n - j + 1) + dp[i - 1][j] * (j - k)\n",
    "        for i in range(1, goal + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] += dp[i - 1][j - 1] * (n - j + 1)\n",
    "                dp[i][j] += dp[i - 1][j] * max((j - k), 0)\n",
    "                dp[i][j] %= MOD\n",
    "        return dp[goal][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "md = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        dp = [[0] * (1+n) for _ in range(1+goal)]\n",
    "\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for i in range(1, goal+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] += dp[i-1][j-1] * (n - j + 1)\n",
    "                dp[i][j] += dp[i-1][j] * (max(j-k, 0))\n",
    "                dp[i][j] = dp[i][j] % md\n",
    "        \n",
    "        return dp[goal][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        dp = [[0]*(n+1) for _ in range(goal+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,goal+1):\n",
    "            for j in range(1,n+1):\n",
    "                dp[i][j] = dp[i-1][j-1]*(n-(j-1)) + dp[i-1][j]*max(j-k,0)\n",
    "                dp[i][j] %= (10**9+7)\n",
    "\n",
    "        return dp[-1][-1]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        # dp[i][j] 长度为i正好包含j首不同歌曲的方案\n",
    "        dp = [[0] * (n + 1) for _ in range(goal + 1)]\n",
    "        # return d[goal - 1][n - 1]\n",
    "        dp[0][0] = 1\n",
    "\n",
    "\n",
    "        for i in range(1, goal + 1):\n",
    "            for j in range(1, n + 1):\n",
    "\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * (n - (j - 1)) + dp[i - 1][j] * (max(j - k, 0))) % MOD\n",
    "\n",
    "        return dp[goal][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        # dp[i][j]表示播放列表长度为i，其中有j首不同的歌时，播放列表的数量\n",
    "        # 对于dp[i][j]，最后一首歌可以是之前没有放过的歌，也可以是放过的\n",
    "        # 1. 没放过的。那么一共有n-(j-1)首没放过的歌，所以dp[i][j]+=dp[i-1][j-1]*(n-j+1)\n",
    "        # 2. 放过的，则前面k首歌需要是不同的歌，能选的歌数量是j-k，dp[i][j] += dp[i-1][j]*max(j-k,0)\n",
    "        dp = [[0]*(n+1) for _ in range(goal+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,goal+1):\n",
    "            for j in range(1,n+1):\n",
    "                dp[i][j] = dp[i-1][j-1] * (n-j+1) + \\\n",
    "                            dp[i-1][j]*max(j-k,0)\n",
    "                dp[i][j]%=MOD\n",
    "        return dp[-1][-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        dp = [[0] * (n + 1) for _ in range(goal + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, goal + 1):\n",
    "            if i <= n:\n",
    "                dp[i][i] = dp[i-1][i-1] * (n - i + 1)\n",
    "            for j in range(1, min(i, n+1)):\n",
    "                dp[i][j] = dp[i-1][j-1] * (n + 1 - j) + dp[i-1][j] * max(j - k, 0)\n",
    "        # print(dp)\n",
    "        return (dp[goal][n] % 1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        dp = [[0]*n for _ in range(goal)]\n",
    "        dp[0][0] = n\n",
    "\n",
    "        if k == 0:\n",
    "            for i in range(1, goal):\n",
    "                dp[i][0] = n\n",
    "\n",
    "        for i in range(1, goal):\n",
    "            for j in range(1, min(i+1, n)):\n",
    "                dp[i][j] = dp[i-1][j-1]*(n-j) + dp[i-1][j]*max(j-k+1, 0)\n",
    "\n",
    "        return dp[-1][-1] % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\r\n",
    "class Solution:\r\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\r\n",
    "        f=[[0]*(goal+1) for _ in range(n+1)]\r\n",
    "        @lru_cache\r\n",
    "        def dp(i,j):\r\n",
    "            if i==0:\r\n",
    "                return 1 if j==0 else 0\r\n",
    "            ans=dp(i-1,j-1)*(n-j+1)\r\n",
    "            ans+=dp(i-1,j)*max(j-k,0)\r\n",
    "            return ans%(10**9+7)\r\n",
    "        return dp(goal,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        mod = (10 ** 9 + 7)\n",
    "        @ cache\n",
    "        def dfs(res, part):\n",
    "            if res == 0:\n",
    "                return 1\n",
    "            if part > n - k:\n",
    "                return 1\n",
    "            if part == n - k: \n",
    "                return pow(part, res) % mod\n",
    "            ans = 0\n",
    "            for i in range(res + 1):\n",
    "                ans += (dfs(res - i, part + 1) * pow(part, i)) % mod\n",
    "            return ans\n",
    "        ans = dfs(goal - n, 1)\n",
    "        for i in range(1, n + 1):\n",
    "            ans *= i\n",
    "            ans %= mod\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "dp = [1] * 101\n",
    "for i in range(2, 101):\n",
    "    dp[i] = (dp[i - 1] * i) % MOD\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i == j:\n",
    "                return dp[i]\n",
    "            if i > j or i <= k:\n",
    "                return 0\n",
    "            return (dfs(i - 1, j - 1) * i + dfs(i, j - 1) * (i - k)) % MOD\n",
    "\n",
    "        return dfs(n, goal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        \n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, r):\n",
    "            if i == goal:\n",
    "                return 1 if r == n else 0\n",
    "            res = 0\n",
    "            if r+1<=n:\n",
    "                res += dfs(i+1, r+1)*(n-r)\n",
    "            if r > k:\n",
    "                res += dfs(i+1, r)*(r-k)    \n",
    "            return res % mod\n",
    "            \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(l,cnt):\n",
    "            if cnt < 0:return 0\n",
    "            if l == 0 and cnt == 0:return 1\n",
    "            if l < cnt:return 0\n",
    "            res = dfs(l-1,cnt-1) * (n-cnt+1)\n",
    "            res += dfs(l-1,cnt) * max(0,cnt-k)\n",
    "            res %= 10**9+7\n",
    "            return res\n",
    "        return dfs(goal,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(goal, old_songs):\n",
    "            if goal == 0 and old_songs == n:\n",
    "                return 1\n",
    "            if goal == 0 or old_songs > n:\n",
    "                return 0\n",
    "            res = (n - old_songs) * dfs(goal - 1, old_songs + 1)\n",
    "            if old_songs > k:\n",
    "                res += (old_songs - k) * dfs(goal - 1, old_songs)\n",
    "            return res % mod\n",
    "\n",
    "        return dfs(goal, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "#         def A(N,m):\n",
    "#             res=1\n",
    "#             for i in range(N, N-m, -1):\n",
    "#                 res*=i\n",
    "#             return res\n",
    "#         def dp(i,j):\n",
    "#             if not i or not j:\n",
    "#                 return 0\n",
    "#             if i==j:\n",
    "#                 return A(n,i)\n",
    "#             a=dp(i-1, j-1)*(n+1-j)\n",
    "#             b=dp(i-1,j)*max(j-k,0)\n",
    "#             return a+b\n",
    "        \n",
    "#         return dp(goal,n)%(10**9+7)\n",
    "\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, N: int, goal: int, k: int) -> int:\n",
    "        def A(n,m):\n",
    "            x=1\n",
    "            for i in range(n,n-m,-1):\n",
    "                x*=i\n",
    "            return x\n",
    "        @cache\n",
    "        def dp(i,j):\n",
    "            '''\n",
    "            播放列表长度为i，正好有j首歌曲的方案数\n",
    "            '''\n",
    "            if not i or not j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return A(N,i)\n",
    "            #选择了新歌\n",
    "            a = dp(i-1,j-1) * (N - j + 1) \n",
    "            #选择了旧歌\n",
    "            b = dp(i-1,j) * max(j-k,0)\n",
    "            return a+b\n",
    "\n",
    "        return dp(goal,N) % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        mod = (10 ** 9 + 7)\n",
    "        @ cache\n",
    "        def dfs(i, j):\n",
    "            if i == 0:\n",
    "                return 1 if j == 0 else 0\n",
    "            if i < j:\n",
    "                return 0\n",
    "            else:\n",
    "                return (dfs(i - 1, j - 1) * (n - j + 1) + dfs(i - 1, j) * max(j - k, 0)) % mod\n",
    "        return dfs(goal, n)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def numMusicPlaylists(self, n, goal, k):\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            if j == 0:\n",
    "                return +(i == 0)\n",
    "            res = dp(i - 1, j - 1) * (n - i + 1)\n",
    "            res += dp(i, j - 1) * max(i - k, 0)\n",
    "            return res % (10 ** 9 + 7)\n",
    "\n",
    "        return dp(n, goal)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        from functools import lru_cache\n",
    "        # goal >= n\n",
    "        # n=3, goal=3, k=1: 6 [1, 2, 3]，[1, 3, 2]，[2, 1, 3]，[2, 3, 1]，[3, 1, 2]，[3, 2, 1] \n",
    "        # n=3, goal=4, k=1: \n",
    "\n",
    "        # n=2, goal=2, k=1: 2 [1,2] [2,1]\n",
    "        # n=2, goal=3, k=1: [1,2,1] [2,1,2]\n",
    "        # n=2, goal=4, k=1: [   ]\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            if i == 0:\n",
    "                return +(j == 0)\n",
    "            ans = dp(i-1, j-1) * (n - j +1)\n",
    "            ans += dp(i-1, j) * max(j - k, 0)\n",
    "            return ans % (10 ** 9 + 7)\n",
    "        return dp(goal, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i==0:\n",
    "                return int(j==0)\n",
    "            ans=dfs(i-1,j-1)*(n-(j-1))\n",
    "            ans+=dfs(i-1,j)*max(j-k,0)\n",
    "            ans%=(10**9+7)\n",
    "            return ans        \n",
    "        return dfs(goal,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def dfs(idx, j):\n",
    "            if idx == 0:\n",
    "                return int(j == 0)\n",
    "            res = 0\n",
    "            res += dfs(idx - 1, j - 1) * (n - j + 1)\n",
    "            res += dfs(idx - 1, j) * max(j - k, 0)\n",
    "            return res % mod\n",
    "        return dfs(goal, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, N, L, K):\n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            if i == 0:\n",
    "                return +(j == 0)\n",
    "            ans = dp(i-1, j-1) * (N-j+1)\n",
    "            ans += dp(i-1, j) * max(j-K, 0)\n",
    "            return ans % (10**9+7)\n",
    "\n",
    "        return dp(L, N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.MOD = 10 ** 9 + 7\n",
    "\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            if i == 0:\n",
    "                return j == 0\n",
    "            res = dp(i - 1, j - 1) * (n - j + 1)\n",
    "            res += dp(i - 1, j) * max(j - k, 0)\n",
    "            return res % self.MOD\n",
    "\n",
    "        return dp(goal, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            if i == 0:\n",
    "                return +(j == 0)\n",
    "            ans = dp(i-1, j-1) * (n-j+1)\n",
    "            ans += dp(i-1, j) * max(j-k, 0)\n",
    "            return ans % (10**9 + 7)\n",
    "\n",
    "        return dp(goal, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        \"\"\" define dfs(i, j) = number of combo for playlist of length i and with j \n",
    "        distinct songs.\n",
    "        if the next song has not been played:\n",
    "            dfs(i, j) = dfs(i-1, j-1) * (n-j+1)\n",
    "        if the next song has been played:\n",
    "            dfs(i, j) = dfs(i-1, j) * max(j-k, 0)\n",
    "        \"\"\" \n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i == 0:\n",
    "                if j == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0 \n",
    "\n",
    "            S1 = dfs(i-1, j-1) * (n-j+1)\n",
    "            S2 = dfs(i-1, j) * max(j-k, 0)\n",
    "\n",
    "            return (S1+S2) % (10**9+7)\n",
    "\n",
    "        return dfs(goal, n) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, N, L, K):\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            if i == 0:\n",
    "                return +(j == 0)\n",
    "            ans = dp(i-1, j-1) * (N-j+1)\n",
    "            ans += dp(i-1, j) * max(j-K, 0)\n",
    "            return ans % (10**9+7)\n",
    "\n",
    "        return dp(L, N)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i == 0:\n",
    "                return j == 0\n",
    "            ans = dfs(i - 1,j - 1) * (n - j + 1)\n",
    "            ans += dfs(i - 1,j) * max(j - k, 0)\n",
    "            return ans % MOD\n",
    "        return dfs(goal,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i == 0:\n",
    "                return +(j == 0)\n",
    "            ans = dfs(i - 1,j - 1)*(n - j + 1)\n",
    "            ans += dfs(i - 1,j)*max(j - k,0)\n",
    "            return ans % MOD\n",
    "        \n",
    "        return dfs(goal,n)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
